package com.leetcode.no39;

import java.util.*;

public class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();

        backtrack(candidates, target, 0, track);

        return res;
    }

    public void backtrack(int[] candidates, int target, int index, LinkedList<Integer> track) {

        // 结束条件
        if (target == 0) {
            res.add(new LinkedList(track));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            // 剪去不合法的分支
            if (candidates[i] > target) {
                continue;
            }
            // 做选择
            track.add(candidates[i]);

            // 进入下一层决策树
            backtrack(
                    candidates,
                    target - candidates[i],
                    i,
                    track
            );

            // 取消选择
            track.removeLast();
        }
    }
}

// 由@liu-li-8提供
class Solution01 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, Set<List<Integer>>> map = new HashMap<>();
        //对candidates数组进行排序
        Arrays.sort(candidates);
        int len = candidates.length;
        for (int i = 1; i <= target; i++) {
            //初始化map
            map.put(i, new HashSet<>());
            //对candidates数组进行循环
            for (int j = 0; j < len && candidates[j] <= target; j++) {
                if (i == candidates[j]) {
                    //相等即为相减为0的情况，直接加入set集合即可
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    map.get(i).add(temp);
                } else if (i > candidates[j]) {
                    //i-candidates[j]是map的key
                    int key = i - candidates[j];
                    //使用迭代器对对应key的set集合进行遍历
                    //如果candidates数组不包含这个key值，对应的set集合会为空，故这里不需要做单独判断
                    for (Iterator iterator = map.get(key).iterator(); iterator.hasNext(); ) {
                        List list = (List) iterator.next();
                        //set集合里面的每一个list都要加入candidates[j]，然后放入到以i为key的集合中
                        List tempList = new ArrayList<>();
                        tempList.addAll(list);
                        tempList.add(candidates[j]);
                        //排序是为了通过set集合去重
                        Collections.sort(tempList);
                        map.get(i).add(tempList);
                    }
                }
            }
        }
        result.addAll(map.get(target));
        return result;
    }
}
